import java.util.Arrays;
/*
* 时间复杂度：O(N)
* 空间复杂度: O(M) : M 表示 当前数据的范围
* 【空间 换 时间】
* 稳定性： 当前代码是不稳定，本质是稳定的。
* 在借助一个 数组来存储 每个 元素的最后一次出现的下标位置
* 拿出来的时候，就能确定位置。致使该排序 稳定。 - 见附图
* */

public class CountingSort {
    public static void countingSort(int[] array){
        int maxVal = array[0];
        int minVal = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] > maxVal){
                maxVal = array[i];
            }
            if(array[i] < minVal){
                minVal =array[i];
            }
        }
        // 当循环结束，获得了 数据的最大值 和 最小值
        // 可以确定计数数组的容量
        int[] count = new int[maxVal -minVal +1];
        for (int i = 0; i < array.length; i++) {
            count[ array[i] - minVal ]++;
        }
        // 此时，计数数组 已经把array数组当中，每个元素的出现次数统计好了
        // 接下来，只需要遍历计数数组，把 数据 覆写 到 array当中。
        int indexArray = 0; // 用于遍历 array数组，标记 覆写的位置。
        for (int i = 0; i < count.length; i++) {
            while(count[i]>0){
                // 这里一定要加上减去minVal，因为 下标 i 不一定 在 array 数组中出现过。
                array[indexArray++] = i + minVal;// 拿出来的时候，记得将减去的值加上
                // indexArray++;
                count[i]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {5,0,2,3,4,5,2};
        countingSort(array);
        System.out.println(Arrays.toString(array));
    }
}
